import java.util.Comparator;

public class QuickSort<T> {

    private Comparator<T> comparator;

    public QuickSort(Comparator<T> comparator) {
        this.comparator = comparator;
    }

    public void sort(T[] array) {
        sort(array, 0, array.length);
    }

    private void sort(T[] array, int low, int high) {
        if (high - low <= 1) {
            return;
        }

        int pivotIndex = partition(array, low, high);

        sort(array, low, pivotIndex);
        sort(array, pivotIndex + 1, high);
    }

    private int partition(T[] array, int begin, int end) {
        T pivot = array[begin + ((end - begin) >>> 1)];
        int low = begin;
        int high = end - 1;

        while (low < high) {
            while (low < high && comparator.compare(array[high], pivot) >= 0) {
                --high;
            }
            array[low] = array[high];

            while (low < high && comparator.compare(array[low], pivot) <= 0) {
                ++low;
            }
            array[high] = array[low];
        }
        array[low] = pivot;

        return low;
    }
}
